package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-26 18:52
 * @description: Functions of this class is
 * 官方题解（归并排序更简洁）：
 * public class Solution {
 *     public int reversePairs(int[] nums) {
 *         int len = nums.length;
 *
 *         if (len < 2) {
 *             return 0;
 *         }
 *
 *         int[] copy = new int[len];
 *         for (int i = 0; i < len; i++) {
 *             copy[i] = nums[i];
 *         }
 *
 *         int[] temp = new int[len];
 *         return reversePairs(copy, 0, len - 1, temp);
 *     }
 *
 *     private int reversePairs(int[] nums, int left, int right, int[] temp) {
 *         if (left == right) {
 *             return 0;
 *         }
 *
 *         int mid = left + (right - left) / 2;
 *         int leftPairs = reversePairs(nums, left, mid, temp);
 *         int rightPairs = reversePairs(nums, mid + 1, right, temp);
 *
 *         if (nums[mid] <= nums[mid + 1]) {
 *             return leftPairs + rightPairs;
 *         }
 *
 *         int crossPairs = mergeAndCount(nums, left, mid, right, temp);
 *         return leftPairs + rightPairs + crossPairs;
 *     }
 *
 *     private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
 *         for (int i = left; i <= right; i++) {
 *             temp[i] = nums[i];
 *         }
 *
 *         int i = left;
 *         int j = mid + 1;
 *
 *         int count = 0;
 *         for (int k = left; k <= right; k++) {
 *
 *             if (i == mid + 1) {
 *                 nums[k] = temp[j];
 *                 j++;
 *             } else if (j == right + 1) {
 *                 nums[k] = temp[i];
 *                 i++;
 *             } else if (temp[i] <= temp[j]) {
 *                 nums[k] = temp[i];
 *                 i++;
 *             } else {
 *                 nums[k] = temp[j];
 *                 j++;
 *                 count += (mid - i + 1);
 *             }
 *         }
 *         return count;
 *     }
 * }
 **/
public class NoNoNo归并排序数组中的逆序对 {
    private static int ans=0;
    public static void main(String args[]){
        int nums[]={5,4,3,2,1};
        mergeSort(nums,0,nums.length-1);
        System.out.println(ans);
    }
    private static void mergeSort(int nums[],int left,int right){
        if(left<right){
            int mid=(left+right)>>1;
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            merge(nums,left,right,mid);
        }
    }
    private static void merge(int nums[],int left,int right,int mid) {
        int i = left;
        int j = mid + 1;
        int sub[] = new int[right - left + 1];
        int index = 0;
        while (i <= mid && j <= right) {
            if (nums[i] >nums[j]) {
                //如果当前左块的元素>右块的元素，则说明产生了序列对
                // 这里不能用>=，是因为如果等于的话，并不能保证说i后面的元素都是大于i，可能是等于i的，会不稳定

                ans += (mid-i + 1);

                //而每当遇到 左子数组当前元素 > 右子数组当前元素 时，
                // 意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
                //所以逆序对贡献就为当前指针下到mid之间的元素个数

                sub[index++] = nums[j++];
            } else {
                sub[index++] = nums[i++];
            }
        }
        while (i <= mid) {
            sub[index++] = nums[i++];
        }
        while (j <= right) {
            sub[index++] = nums[j++];

        }
        index=0;
        for(int k=left;k<=right;k++){
            nums[k]=sub[index++];
        }
    }
}